package class001_010;

/**
 * ClassName: Code10_MergeTwoLists
 * Package: class001_010
 * Description:
 *
 * @Author s
 * @Create 2025/7/24 15:59
 * @Version 1.0
 */
public class Code10_MergeTwoLists {

    // 不要提交这个类
    public static class ListNode {
        public int val;
        public ListNode next;

        public ListNode(int val) {
            this.val = val;
        }

        public ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    public static ListNode mergeTwoLists(ListNode head1, ListNode head2) {
        if (head1 == null || head2 == null) {
            return head1 == null ? head2 : head1;
        }

        ListNode head = head1.val <= head2.val ? head1 : head2; // 最终返回
        ListNode cur1 = head.next; // 链表1的游标
        ListNode cur2 = head == head1 ? head2 : head1; // 链表2的游标
        ListNode pre = head; // 跟着动的头

        while (cur1 != null && cur2 != null) {
            if (cur1.val <= cur2.val) {
                pre.next = cur1;
                cur1 = cur1.next;
            } else {
                pre.next = cur2;
                cur2 = cur2.next;
            }
            pre = pre.next;
        }

        pre.next = cur1 != null ? cur1 : cur2;

        return head;
    }

}
